home *** CD-ROM | disk | FTP | other *** search
/ Megadoom II / MEGADOOM II - iso.7z / MEGADOOM II.ISO / doom / editors / wadfile / warm11 / nodes.c < prev    next >
C/C++ Source or Header  |  1995-01-18  |  30KB  |  750 lines
  1. /******************************************************************************
  2.     MODULE:        NODES.C
  3.     WRITTEN BY:    Robert Fenske, Jr. (rfenske@swri.edu)
  4.                 Southwest Research Institute
  5.                 Electromagnetics Division
  6.                 6220 Culebra
  7.                 San Antonio, Texas 78238-5166
  8.     CREATED:    Mar. 1994
  9.     DESCRIPTION:    This module contains routines to generate the SEGS,
  10.             SSECTORS, and NODES sections.  It needs only the
  11.             LINEDEFS and VERTEXES as input.  These three sections
  12.             combine to form a binary space partition tree.  This
  13.             tree is built by recursively dividing the space into
  14.             sections that balance (or at least try to) the number
  15.             of segments and produce the least number of segment
  16.             splits.  The nodes are kept in a binary tree.  The
  17.             segments are kept in an ordered doubly-linked list.
  18.             The created vertices are added to the end of the
  19.             vertex list.  Once the divisions are complete, the
  20.             SEGS, SSECTORS, and NODES structures are created from
  21.             the binary tree and the segment and vertex lists.  Any
  22.             memory allocated for the binary tree or the linked
  23.             list is freed when no longer needed.
  24.  
  25.             This module does not do any error checking on any
  26.             memory allocation.  If any allocation ever fails, this
  27.             module will bomb.
  28.  
  29.             This module used to do some error checking while
  30.             building the node tree, but now the tree is generated
  31.             regardless of whether the input describes a correct,
  32.             playable map.
  33.  
  34.             I wrote the code from the description of the binary
  35.             space partition in the Unofficial DOOM Specs written
  36.             by Matt Fell.  I found these references after I did
  37.             the coding:
  38.  
  39.             1) Computer Graphics Principles and Practice,
  40.                2nd ed 1990
  41.                Foley J.D., van Dam A., Feiner S.K., Hughes J.F.
  42.                ISBN 0-201-12110-7
  43.  
  44.             2) "On Visible Surface Generation by a Priori Tree
  45.                Structures"
  46.                Fuchs H., Kedem Z.M., Naylor B.F.
  47.                Computer Graphics (SIGGRAPH '80 Proceedings)
  48.                v14 #3 July 1980 pp 124-133
  49.  
  50.             3) "Near Real-Time Shaded Display of Rigid Objects"
  51.                Fuchs H., Abram G.D., Grant E.D.
  52.                Computer Graphics (SIGGRAPH '83 Proceesings)
  53.                v17 #3 July 1983 pp 65-72
  54.  
  55.             DOOM is a trademark of id Software, Inc.
  56. ******************************************************************************/
  57. #include <stdio.h>
  58. #include <stdlib.h>
  59. #if !defined(__OS2__)
  60. #include <values.h>
  61. #endif
  62. #include <math.h>
  63. #include "dmglobal.i"
  64.  
  65. #if defined(__OS2__)
  66. #define M_SQRT2        1.41421356237309504880
  67. #endif
  68.  
  69. #define tree_branch(c)    ((c)=blockmem(NODE_TREE,1), \
  70.              (c)->left=NULL, (c)->right=NULL, (c))
  71. #define two_sided(l)    (lines[l].lsidndx != -1)
  72. #define vdist2(v1,v2)    (((long)(v1).x-(v2).x)*((long)(v1).x-(v2).x)+\
  73.              ((long)(v1).y-(v2).y)*((long)(v1).y-(v2).y))
  74.  
  75.  
  76. typedef struct SEGS_INFO {
  77.     DOOM_SEGS seg;                /* a SEGment */
  78.     struct SEGS_INFO *prev, *next;        /* to previous, next SEGment */
  79. } SEGS_INFO;
  80.  
  81. typedef struct NODE_TREE {
  82.     short ymin, ymax, xmin, xmax;        /* node rectangle limits */
  83.     SEGS_INFO *pseg;            /* partition line SEG */
  84.     SEGS_INFO *segs;            /* node's SEGS */
  85.     short nsegs;                /* # initial SEGS in node */
  86.     struct NODE_TREE *left, *right;        /* left, right children */
  87. } NODE_TREE;
  88.  
  89. typedef struct NODE_INFO {
  90.     DOOM_NODE *nodes;            /* all nodes */
  91.     int nnodes;                /* total # NODES */
  92.     DOOM_VERT *sverts;            /* all SEGS vertices */
  93.     int nsverts;                /* total # SEGS vertices */
  94.     DOOM_SEGS *segs;            /* all nodes' SEGS */
  95.     int nsegs;                /* total # segs */
  96.     DOOM_SSECTOR *ssecs;            /* all nodes' SSECTORs */
  97.     int nssecs;                /* total # SSECTORs */
  98.     SEGS_INFO *sinfo;            /* all SEGS lists */
  99. } NODE_INFO;
  100.  
  101. local NODE_INFO ninfo;                /* node information */
  102.  
  103.  
  104. /******************************************************************************
  105.     ROUTINE:    nodes_segs_init(lines,nlines)
  106.     WRITTEN BY:    Robert Fenske, Jr.
  107.     CREATED:    Mar. 1994
  108.     DESCRIPTION:    This routine initializes the SEGS list by scanning the
  109.             LINEDEFS list and creating the appropriate SEGS
  110.             entries.  A seg is created for each side a LINEDEF has.
  111.             It returns the number of SEGS created.
  112. ******************************************************************************/
  113. #if defined(ANSI_C)
  114. local int nodes_segs_init(register DOOM_LINE *lines, long nlines)
  115. #else
  116. local int nodes_segs_init(lines,nlines)
  117. register DOOM_LINE *lines;
  118. long nlines;
  119. #endif
  120. {
  121.   DOOM_VERT *vf, *vt;
  122.   register SEGS_INFO *sinfo;
  123.   register int nsegs;
  124.   register int l;
  125.  
  126.   nsegs = 0;
  127.   ninfo.sinfo = sinfo = blockmem(SEGS_INFO,1);
  128.   sinfo->prev = NULL;
  129.   for (l = 0; l < nlines; l++) {        /* scan all lines */
  130.     sinfo->seg.fndx = lines[l].fndx;
  131.     sinfo->seg.tndx = lines[l].tndx;
  132.     vf = &ninfo.sverts[sinfo->seg.fndx], vt = &ninfo.sverts[sinfo->seg.tndx];
  133.     sinfo->seg.angle = (bams)(vt->y==vf->y && vt->x<vf->x ? BAMS180 :
  134.                               atan2((double)(vt->y-vf->y),
  135.                                     (double)(vt->x-vf->x))*rad_to_bams+
  136.                               0.5*sgn(vt->y-vf->y));
  137.     sinfo->seg.sndx = 0;            /* right side */
  138.     sinfo->seg.lndx = l;
  139.     sinfo->seg.loffset = 0;
  140.     nsegs++;
  141.     sinfo->next = blockmem(SEGS_INFO,1);    /* set up for next one */
  142.     sinfo->next->prev = sinfo;
  143.     sinfo = sinfo->next;
  144.     if (two_sided(l)) {                /* a left side also */
  145.       sinfo->seg.fndx = lines[l].tndx;        /* switch vertices */
  146.       sinfo->seg.tndx = lines[l].fndx;
  147.       sinfo->seg.angle = sinfo->prev->seg.angle+BAMS180;
  148.       sinfo->seg.sndx = 1;            /* left side */
  149.       sinfo->seg.lndx = l;
  150.       sinfo->seg.loffset = 0;
  151.       nsegs++;
  152.       sinfo->next = blockmem(SEGS_INFO,1);    /* set up for next one */
  153.       sinfo->next->prev = sinfo;
  154.       sinfo = sinfo->next;
  155.     }
  156.   }
  157.   sinfo->prev->next = NULL;
  158.   blockfree(sinfo);                /* don't need this one */
  159.   return nsegs;                    /* return # created SEGS */
  160. }
  161.  
  162.  
  163. /******************************************************************************
  164.     ROUTINE:    nodes_split_seg(pseg,seg,right,left)
  165.     WRITTEN BY:    Robert Fenske, Jr.
  166.     CREATED:    Mar. 1994
  167.     DESCRIPTION:    This routine splits the input segment into left and
  168.             right segments based on the input partition line.  The
  169.             intersection of the partition line (based on the input
  170.             "from" and "to" coordinates) with the segment is found
  171.             so that a new vertex can be added to the vertex list.
  172.             The offset field of the left and right segments are
  173.             computed from the distance to the new vertex along the
  174.             segment.
  175. ******************************************************************************/
  176. #if defined(ANSI_C)
  177. local void nodes_split_seg(SEGS_INFO *pseg, SEGS_INFO *seg,
  178.                            register SEGS_INFO **right,
  179.                            register SEGS_INFO **left)
  180. #else
  181. local void nodes_split_seg(pseg,seg,right,left)
  182. SEGS_INFO *pseg, *seg;
  183. register SEGS_INFO **right, **left;
  184. #endif
  185. {
  186.   DOOM_VERT *pf = &ninfo.sverts[pseg->seg.fndx],
  187.             *pt = &ninfo.sverts[pseg->seg.tndx],
  188.             *vf = &ninfo.sverts[seg->seg.fndx],
  189.             *vt = &ninfo.sverts[seg->seg.tndx];
  190.   long Ap = -((long)pt->y - pf->y),        /* partition line is */
  191.        Bp = (long)pt->x - pf->x,        /* Ax + By + C = 0   */
  192.        Cp = (long)pt->y*pf->x - (long)pt->x*pf->y;
  193.   long As = -((long)vt->y - vf->y),        /* SEG line is     */
  194.        Bs = (long)vt->x - vf->x,        /* Ax + By + C = 0 */
  195.        Cs = (long)vt->y*vf->x - (long)vt->x*vf->y;
  196.   double x, y;                    /* intersection coords */
  197.   DOOM_VERT iv;                    /* intersection vertex */
  198.   register int v;                /* intersection vertex index */
  199.  
  200.   *right = blockmem(SEGS_INFO,1);        /* new right side SEG */
  201.   (*right)->seg = seg->seg;
  202.   (*right)->next = NULL;
  203.   *left = blockmem(SEGS_INFO,1);        /* new left side SEG */
  204.   (*left)->seg = seg->seg;
  205.   (*left)->next = NULL;
  206.   x =  ((double)Bs*Cp - (double)Bp*Cs)/((double)Bp*As - (double)Bs*Ap);
  207.   y = -((double)As*Cp - (double)Ap*Cs)/((double)Bp*As - (double)Bs*Ap);
  208.   iv.x = x + sgn(x)*0.5;
  209.   iv.y = y + sgn(y)*0.5;
  210.   ninfo.sverts[v = ninfo.nsverts++] = iv;    /* add new vertex to list */
  211.   if (seg->seg.sndx == 0) {            /* this is a right side SEG */
  212.     if (Ap*vf->x + Bp*vf->y + Cp < 0) {
  213.       (*right)->seg.tndx = v;
  214.       (*left)->seg.fndx = v;
  215.       (*left)->seg.loffset = seg->seg.loffset + sqrt((double)vdist2(*vf,iv));
  216.     }else {
  217.       (*right)->seg.fndx = v;
  218.       (*right)->seg.loffset = seg->seg.loffset + sqrt((double)vdist2(*vt,iv));
  219.       (*left)->seg.tndx = v;
  220.     }
  221.   }else {                    /* this is a left side SEG */
  222.     if (Ap*vt->x + Bp*vt->y + Cp < 0) {
  223.       (*right)->seg.fndx = v;
  224.       (*right)->seg.loffset = seg->seg.loffset + sqrt((double)vdist2(*vt,iv));
  225.       (*left)->seg.tndx = v;
  226.     }else {
  227.       (*right)->seg.tndx = v;
  228.       (*left)->seg.fndx = v;
  229.       (*left)->seg.loffset = seg->seg.loffset + sqrt((double)vdist2(*vf,iv));
  230.     }
  231.   }
  232. }
  233.  
  234.  
  235. /******************************************************************************
  236.     ROUTINE:    nodes_insert_seg(seglist,seg,preinsert)
  237.     WRITTEN BY:    Robert Fenske, Jr.
  238.     CREATED:    Mar. 1994
  239.     DESCRIPTION:    This routine inserts the input SEG into the SEGS list
  240.             either before or after the SEG that seglist references,
  241.             depending on the preinsert flag.
  242. ******************************************************************************/
  243. #if defined(ANSI_C)
  244. local void nodes_insert_seg(register SEGS_INFO *seglist,
  245.                             register SEGS_INFO *seg,
  246.                             int preinsert)
  247. #else
  248. local void nodes_insert_seg(seglist,seg,preinsert)
  249. register SEGS_INFO *seglist, *seg;
  250. int preinsert;
  251. #endif
  252. {
  253.   if (preinsert) {                /* insert before */
  254.     seg->prev = seglist->prev;
  255.     seg->next = seglist;
  256.   }else {                    /* insert after */
  257.     seg->prev = seglist;
  258.     seg->next = seglist->next;
  259.   }
  260.   if (seg->prev != NULL) seg->prev->next = seg;
  261.   if (seg->next != NULL) seg->next->prev = seg;
  262. }
  263.  
  264.  
  265. /******************************************************************************
  266.     ROUTINE:    nodes_segs_bounds(node)
  267.     WRITTEN BY:    Robert Fenske, Jr.
  268.     CREATED:    Mar. 1994
  269.     DESCRIPTION:    This routine scans all the SEGS contained in the input
  270.             node to find the minimum and maximum coordinates for
  271.             the node boundaries.
  272. ******************************************************************************/
  273. #if defined(ANSI_C)
  274. local void nodes_segs_bounds(register NODE_TREE *node)
  275. #else
  276. local void nodes_segs_bounds(node)
  277. register NODE_TREE *node;
  278. #endif
  279. {
  280.   register SEGS_INFO *sinfo;
  281.   register DOOM_VERT *vf, *vt;
  282.   register int s;
  283.  
  284.   node->xmin = node->ymin = ~(-1<<(8*sizeof(node->xmin)-1));
  285.   node->xmax = node->ymax = -node->xmin;
  286.   for (sinfo = node->segs, s = 0; s < node->nsegs; s++) {
  287.     vf = &ninfo.sverts[sinfo->seg.fndx], vt = &ninfo.sverts[sinfo->seg.tndx];
  288.     if (vf->x < node->xmin) node->xmin = vf->x;
  289.     if (vf->y < node->ymin) node->ymin = vf->y;
  290.     if (vt->x < node->xmin) node->xmin = vt->x;
  291.     if (vt->y < node->ymin) node->ymin = vt->y;
  292.     if (node->xmax < vf->x) node->xmax = vf->x;
  293.     if (node->ymax < vf->y) node->ymax = vf->y;
  294.     if (node->xmax < vt->x) node->xmax = vt->x;
  295.     if (node->ymax < vt->y) node->ymax = vt->y;
  296.     sinfo = sinfo->next;
  297.   }
  298. }
  299.  
  300.  
  301. /******************************************************************************
  302.     ROUTINE:    nodes_select_side(pseg,seg)
  303.     WRITTEN BY:    Robert Fenske, Jr.
  304.     CREATED:    Mar. 1994
  305.     DESCRIPTION:    This routine returns whether the input segment is
  306.             on the right side, left side, or both sides of the
  307.             partition line of the input node.  This is done by
  308.             determining on which side of the partition line each
  309.             vertex of the seg lies.  Given that the partition line
  310.             is Ax + By + C = 0 and a vertex is (Vx,Vy), the
  311.             intersection of the partition line and the shortest-
  312.             distance line from the vertex to the partition line
  313.             is given by
  314.                 Xi = Vx - b * d
  315.                 Yi = Vy - a * d
  316.             where a = B/(A^2+B^2)^.5, b = A/(A^2+B^2)^.5,
  317.             c = C/(A^2+B^2)^.5, and d = a*Vx + b*Vy + c.  Since
  318.             the directional information can be obtained from
  319.             Xi - Vx = Vx - b*d - Vx = -b*d and
  320.             Yi - Vx = Vy - a*d - Vy = -a*d, only d is needed to
  321.             determine which side the vertex lies on.  Thus only
  322.             the sign (-1, 0, or +1) of d = (A*Vx + B*Vy + C) /
  323.             (A^2 + B^2)^.5 needs to be considered.  This simple
  324.             matrix can be used to determine the side:
  325.                 "from"       "to" vertex
  326.                 vertex    left    on    right
  327.  
  328.                 left    left    left    both
  329.                 on    left    ?    right
  330.                 right    both    right    right
  331.             For the ? case, the side information in the seg must
  332.             be used to determine the "sidedness".  Right is denoted
  333.             with 0, left denoted by 1, and both denoted by -1.
  334.             A, B, C, and d are calculated only when required to
  335.             enhance the speed of the routine.
  336. ******************************************************************************/
  337. #if defined(ANSI_C)
  338. local int nodes_select_side(DOOM_SEGS *pseg, DOOM_SEGS *seg)
  339. #else
  340. local int nodes_select_side(pseg,seg)
  341. DOOM_SEGS *pseg, *seg;
  342. #endif
  343. {
  344.   static int rightleft[3][3] = { {  1,  1, -1 },
  345.                                  {  1, -2,  0 },
  346.                                  { -1,  0,  0 } };
  347.   static DOOM_VERT *lpf = NULL, *lpt = NULL;    /* last partition line verts */
  348.   static long A, B, C;                /* describes partition line */
  349.   static long pd;
  350.   DOOM_VERT *pf = &ninfo.sverts[pseg->fndx],    /* partition line vertices */
  351.             *pt = &ninfo.sverts[pseg->tndx],
  352.             *vf = &ninfo.sverts[seg->fndx],    /* segment vertices */
  353.             *vt = &ninfo.sverts[seg->tndx];
  354.   long pfd, ptd;
  355.   int sideflag;
  356.   register int fside, tside;            /* "from"/"to" vertex side */
  357.  
  358.   if (lpf != pf || lpt != pt) {            /* update A,B,C if have to */
  359.     A = -((long)pt->y - pf->y);            /* partition line is */
  360.     B = (long)pt->x - pf->x;            /* Ax + By + C = 0   */
  361.     C = (long)pt->y*pf->x - (long)pt->x*pf->y;
  362.     pd = (long)(sqrt((double)A*A+(double)B*B)/M_SQRT2+0.5);
  363.     lpf = pf;                    /* save new vertices */
  364.     lpt = pt;
  365.   }
  366.   pfd = A*vf->x + B*vf->y + C;
  367.   fside = (pfd>=0)-(pfd<=-0);            /* "from" vertex side */
  368.   ptd = A*vt->x + B*vt->y + C;
  369.   tside = (ptd>=0)-(ptd<=-0);            /* "to" vertex side */
  370.   sideflag = rightleft[1-fside][1-tside];
  371.   if (sideflag == -1) {                /* test again for "both" */
  372.     fside = (pfd>=pd)-(pfd<=-pd);        /* "from" vertex side */
  373.     tside = (ptd>=pd)-(ptd<=-pd);        /* "to" vertex side */
  374.     sideflag = rightleft[1-fside][1-tside];
  375.   }
  376.   if (sideflag == -2)                /* need to determine based */
  377.     sideflag = pseg->angle != seg->angle;    /* on direction            */
  378.   return sideflag;
  379. }
  380.  
  381.  
  382. /******************************************************************************
  383.     ROUTINE:    nodes_divide_node(node,left,right)
  384.     WRITTEN BY:    Robert Fenske, Jr.
  385.     CREATED:    Mar. 1994
  386.     DESCRIPTION:    This routine divides the input node into left and
  387.             right nodes based on the partition line of the input
  388.             node.  This essentially means that the list of SEGS
  389.             associated with the input node must be divided into
  390.             left and right collections of SEGS.  This division is
  391.             done by moving all the left side SEGS to the end of
  392.             the SEGS list, leaving all right side SEGS at the front
  393.             of the list.  Those SEGS that need to be split have
  394.             their new right side SEG take the position of the old
  395.             SEG and their new left side SEG put at the end of the
  396.             list.  Once the list is divided, the right and left
  397.             nodes are set the appropriate section of the list and
  398.             their bounds are computed.
  399. ******************************************************************************/
  400. #if defined(ANSI_C)
  401. local void nodes_divide_node(register NODE_TREE *node, NODE_TREE *right,
  402.                              NODE_TREE *left)
  403. #else
  404. local void nodes_divide_node(node,right,left)
  405. register NODE_TREE *node;
  406. NODE_TREE *right, *left;
  407. #endif
  408. {
  409.   int sideflag;
  410.   int i;
  411.   SEGS_INFO *next, *end;
  412.   SEGS_INFO *lseg, *rseg;            /* for splitting seg in two */
  413.   register SEGS_INFO *sinfo;
  414.  
  415.   sinfo = node->segs;
  416.   right->nsegs = left->nsegs = 0;
  417.   for (end = sinfo, i = 0; i < node->nsegs-1; i++) end = end->next;
  418.   for (i = 0; i < node->nsegs; i++) {        /* scan all node's SEGS */
  419.     sideflag = nodes_select_side(&node->pseg->seg,&sinfo->seg);
  420.     next = sinfo->next;
  421.     switch (sideflag) {
  422.       case   0: right->nsegs++;            /* just add to right's total */
  423.       bcase  1: if (sinfo->prev != NULL)    /* move to end of list */
  424.                   sinfo->prev->next = sinfo->next;
  425.                 if (sinfo->next != NULL)
  426.                   sinfo->next->prev = sinfo->prev;
  427.                 if (end == sinfo) end = sinfo->prev;
  428.                 if (node->segs == sinfo) node->segs = sinfo->next;
  429.                 nodes_insert_seg(end,sinfo,FALSE);
  430.                 end = sinfo;
  431.                 left->nsegs++;
  432.       bcase -1: nodes_split_seg(node->pseg,sinfo,&rseg,&lseg);
  433.                 sinfo->seg = rseg->seg;        /* make this the right SEG */
  434.                 right->nsegs++;
  435.                 blockfree(rseg);        /* don't need this now */
  436.                 nodes_insert_seg(end,lseg,FALSE);/* add left SEG to end */
  437.                 end = lseg;
  438.                 left->nsegs++;
  439.                 ninfo.nsegs++;            /* one more for total */
  440.     }
  441.     sinfo = next;
  442.   }
  443.   for (sinfo = node->segs, i = 0; i < right->nsegs; i++)
  444.     sinfo = sinfo->next;
  445.   right->segs = node->segs;            /* SEGS on right side of   */
  446.   nodes_segs_bounds(right);            /* partition line are here */
  447.   left->segs = sinfo;                /* EGS on left side of     */
  448.   nodes_segs_bounds(left);            /* partition line are here */
  449. }
  450.  
  451.  
  452. /******************************************************************************
  453.     ROUTINE:    nodes_partition_line(node)
  454.     WRITTEN BY:    Robert Fenske, Jr.
  455.     CREATED:    Mar. 1994
  456.     DESCRIPTION:    This routine searches for a suitable SEG to use as a
  457.             partition line (which will divide the input node).
  458.             Suitable is taken to mean the SEG that most equalizes
  459.             the number of SEGS on each side of the partition line
  460.             and mimimizes the number of SEG splits that need to be
  461.             done.  Ideally, the partition line should also do
  462.             this for all the node's children as well, but the
  463.             calculations would be far too time consuming; therefore
  464.             only the input node is considered.  The most suitable
  465.             partition is found by selecting the SEG that maximizes
  466.             the (geometric mean)^2 of the right and left side
  467.             counts and the number of splits.  The geometric mean
  468.             is computed via A*Rc*Lc/(B*Sc+1) where Rc, Lc, Sc
  469.             are the right side, left side, and split counts
  470.             respectively and A, B are empirical constants (the
  471.             +1 is for the split count zero case).  The geometric
  472.             mean variable is initialized to -1 so that at least
  473.             one SEG will qualify (even if the maximum mean is
  474.             zero).  This routine sets the node's partition line
  475.             to be the SEG that creates the best (maximum) geometric
  476.             mean.
  477. ******************************************************************************/
  478. #if defined(ANSI_C)
  479. local void nodes_partition_line(register NODE_TREE *node)
  480. #else
  481. local void nodes_partition_line(node)
  482. register NODE_TREE *node;
  483. #endif
  484. {
  485.   long bgm = -1L;                /* max geometric mean count */
  486.   long gm;                    /* geometric mean count */
  487.   int rcnt, lcnt, splits;
  488.   char *linetry = blockmem(char,ninfo.nsegs);    /* lines used flags */
  489.   register int sideflag;
  490.   register SEGS_INFO *sinfo, *iseg;
  491.   register int s, i;
  492.  
  493.   sinfo = node->segs;
  494.   for (s = 0; s < node->nsegs; s++) {        /* scan SEGS in node */
  495.     printf(s&1?"/\010":"\\\010");
  496.     if (!linetry[sinfo->seg.lndx]) {        /* try as partition line  */
  497.       rcnt = lcnt = splits = 0;
  498.       iseg = node->segs;
  499.       for (i = 0; i < node->nsegs; i++) {    /* get SEGS pos w.r.t. pseg */
  500.         sideflag = nodes_select_side(&sinfo->seg,&iseg->seg);
  501.         if (sideflag == 0)       rcnt++;    /* count SEGS on both sides */
  502.         else if (sideflag == 1)  lcnt++;    /* of the partition line    */
  503.         else if (sideflag == -1) splits++;
  504.         iseg = iseg->next;
  505.       }
  506.       gm = rcnt*lcnt/(17*splits/3+1);        /* 1, 17/3 are empirical */
  507.       if (rcnt != node->nsegs)
  508.         if (bgm < gm)
  509.           bgm = gm, node->pseg = sinfo;        /* best partition so far */
  510.       linetry[sinfo->seg.lndx] = TRUE;        /* now have tried this line */
  511.     }
  512.     sinfo = sinfo->next;
  513.   }
  514.   blockfree(linetry);                /* done with this */
  515. }
  516.  
  517.  
  518. /******************************************************************************
  519.     ROUTINE:    nodes_subsector_test(node)
  520.     WRITTEN BY:    Robert Fenske, Jr.
  521.     CREATED:    Mar. 1994
  522.     DESCRIPTION:    This routine checks whether the input node can be
  523.             an SSECTOR or not.  To be a subsector, the SEGS in
  524.             the node must describe a convex polygon (no interior
  525.             angles > 180 degrees).  This is equivalent to having
  526.             all the SEGS on the right side of each other.
  527. ******************************************************************************/
  528. #if defined(ANSI_C)
  529. local int nodes_subsector_test(register NODE_TREE *node)
  530. #else
  531. local int nodes_subsector_test(node)
  532. register NODE_TREE *node;
  533. #endif
  534. {
  535.   int subsector = TRUE;
  536.   register SEGS_INFO *sinfo, *iseg;
  537.   register int s, i;
  538.  
  539.   sinfo = node->segs;
  540.   for (s = 0; subsector && s < node->nsegs; s++) {/* scan all SEGS */
  541.     for (iseg = node->segs, i = 0; i < node->nsegs; i++) {
  542.       if (i != s) {
  543.         if (nodes_select_side(&sinfo->seg,&iseg->seg) != 0) {
  544.           subsector = FALSE;            /* interior angle > 180 degs */
  545.           break;                /* so not an SSECTOR         */
  546.         }
  547.       }
  548.       iseg = iseg->next;
  549.     }
  550.     sinfo = sinfo->next;
  551.   }
  552.   return subsector;
  553. }
  554.  
  555.  
  556. /******************************************************************************
  557.     ROUTINE:    nodes_partition_node(node)
  558.     WRITTEN BY:    Robert Fenske, Jr.
  559.     CREATED:    Mar. 1994
  560.     DESCRIPTION:    This routine performs the binary space partitioning.
  561.             It recursively divides (partitions) the input node
  562.             until each leaf of the subtree defined by the input
  563.             node is an SSECTOR.  A partition line is obtained and
  564.             the left and right subtrees are allocated.  The left
  565.             subtree is always checked first.  If it is not an
  566.             SSECTOR, a recursive call is made to further divide
  567.             the left subtree.  The same procedure is then performed
  568.             on the right subtree.  The number of left and right
  569.             children plus one for the current node is returned.
  570. ******************************************************************************/
  571. #if defined(ANSI_C)
  572. local int nodes_partition_node(register NODE_TREE *node)
  573. #else
  574. local int nodes_partition_node(node)
  575. register NODE_TREE *node;
  576. #endif
  577. {
  578.   int nl, nr;                    /* # left, right nodes */
  579.   register NODE_TREE *left, *right;        /* left, right children */
  580.  
  581.   nodes_partition_line(node);            /* obtain partition line */
  582.   node->right = tree_branch(right);
  583.   node->left = tree_branch(left);
  584.   nodes_divide_node(node,right,left);
  585.   if (nodes_subsector_test(left)) {        /* found an SSECTOR */
  586.     printf("*\010\010");
  587.     nl = 1;
  588.   }else {                    /* need further subdivision */
  589.     printf("L");
  590.     nl = nodes_partition_node(left);
  591.   }
  592.   if (nodes_subsector_test(right)) {        /* found an SSECTOR */
  593.     printf("*\010\010");
  594.     nr = 1;
  595.   }else {                    /* need further subdivision */
  596.     printf("R");
  597.     nr = nodes_partition_node(right);
  598.   }
  599.   return nl + nr + 1;                /* # left + # right + this 1 */
  600. }
  601.  
  602.  
  603. /******************************************************************************
  604.     ROUTINE:    nodes_place_node(nodes,nndx,sndx,nodetree)
  605.     WRITTEN BY:    Robert Fenske, Jr.
  606.     CREATED:    Mar. 1994
  607.     DESCRIPTION:    This routine builds the NODES structure from the
  608.             input node tree.  It traverses the node tree in a
  609.             post-order fashion, left side first.  As the tree is
  610.             scanned, the NODES, SSECTORS, and SEGS lists are filled
  611.             in as appropriate.  The SSECTORS and SEGS lists are
  612.             referenced through the ninfo block.  The node tree
  613.             entries are deleted after they are used.  The node
  614.             number (or index) is returned, unless an SSECTOR is
  615.             found, then a -(SSECTOR number) is returned.
  616. ******************************************************************************/
  617. #if defined(ANSI_C)
  618. local int nodes_place_node(register DOOM_NODE *nodes, int *nndx, int *sndx,
  619.                            register NODE_TREE *nodetree)
  620. #else
  621. local int nodes_place_node(nodes,nndx,sndx,nodetree)
  622. register DOOM_NODE *nodes;
  623. int *nndx, *sndx;
  624. register NODE_TREE *nodetree;
  625. #endif
  626.  
  627. {
  628.   int nnum;                    /* node number to return */
  629.   int lnum, rnum;
  630.   SEGS_INFO *sinfo, *next;
  631.   register DOOM_NODE *node;
  632.   register int s;
  633.  
  634.   if (nodetree->left != NULL) {            /* traverse node subtree */
  635.     lnum = nodes_place_node(nodes,nndx,sndx,nodetree->left);
  636.     rnum = nodes_place_node(nodes,nndx,sndx,nodetree->right);
  637.     node = &nodes[nnum = (*nndx)++];
  638.     node->x = ninfo.sverts[nodetree->pseg->seg.fndx].x;/* these 4 describe   */
  639.     node->y = ninfo.sverts[nodetree->pseg->seg.fndx].y;/* the partition line */
  640.     node->xdel = ninfo.sverts[nodetree->pseg->seg.tndx].x - node->x;
  641.     node->ydel = ninfo.sverts[nodetree->pseg->seg.tndx].y - node->y;
  642.     node->lymax = nodetree->left->ymax;
  643.     node->lymin = nodetree->left->ymin;
  644.     node->lxmin = nodetree->left->xmin;
  645.     node->lxmax = nodetree->left->xmax;
  646.     if (lnum < 0) node->nndx[1] = 0x8000 | (-lnum-1);/* mark as SSECTOR */
  647.     else          node->nndx[1] = lnum;        /* mark as NODE */
  648.     blockfree(nodetree->left);            /* done with left subtree */
  649.     node->rymax = nodetree->right->ymax;
  650.     node->rymin = nodetree->right->ymin;
  651.     node->rxmin = nodetree->right->xmin;
  652.     node->rxmax = nodetree->right->xmax;
  653.     if (rnum < 0) node->nndx[0] = 0x8000 | (-rnum-1);/* mark as SSECTOR */
  654.     else          node->nndx[0] = rnum;        /* mark as NODE */
  655.     blockfree(nodetree->right);            /* done with right subtree */
  656.   }else {                    /* SSECTOR (tree leaf) */
  657.     ninfo.ssecs[*sndx].count = nodetree->nsegs;
  658.     if (*sndx == 0) ninfo.ssecs[*sndx].sndx = 0;
  659.     else            ninfo.ssecs[*sndx].sndx = ninfo.ssecs[*sndx-1].sndx+
  660.                                               ninfo.ssecs[*sndx-1].count;
  661.     sinfo = nodetree->segs;
  662.     for (s = 0; s < nodetree->nsegs; s++) {    /* copy node's SEGS to full */
  663.       ninfo.segs[ninfo.nsegs++] = sinfo->seg;    /* SEGS array               */
  664.       next = sinfo->next;
  665.       blockfree(sinfo);
  666.       sinfo = next;
  667.     }
  668.     nnum = -++(*sndx);                /* mark as leaf */
  669.   }
  670.   return nnum;                    /* ret node # or <0 if leaf */
  671. }
  672.  
  673.  
  674. /******************************************************************************
  675.     ROUTINE:    nodes_make(nodes,nnodes,ssecs,nssecs,segs,nsegs,
  676.                        verts,nverts,lines,nlines)
  677.     WRITTEN BY:    Robert Fenske, Jr.
  678.     CREATED:    Mar. 1994
  679.     DESCRIPTION:    This routine generates the NODES, SSECTORS, and SEGS
  680.             sections.  It first finds the minimum and maximum x,y
  681.             coordinates of the map to use in the root of the node
  682.             tree.  Then the node tree root is created.  The
  683.             necessary counters in the ninfo block are zeroed and
  684.             the SEGS vertices list is allocated.  Then
  685.             nodes_partition_node() is called to build the node
  686.             tree.  Next, the NODES, SSECTORS, and SEGS lists are
  687.             allocated based on the values calculated during the
  688.             construction of the node tree.  The necessary counters
  689.             are zeroed and nodes_place_node() is called to fill
  690.             the NODES, SSECTORS, and SEGS lists with the correct
  691.             information.  All the appropriate values are placed
  692.             into the return variables and the number of computed
  693.             node entries is returned.
  694. ******************************************************************************/
  695. #if defined(ANSI_C)
  696. long nodes_make(DOOM_NODE **nodes, long *nnodes, DOOM_SSECTOR **ssecs,
  697.                long *nssecs, DOOM_SEGS **segs, long *nsegs,
  698.                DOOM_VERT **verts, long *nverts, DOOM_LINE **lines,
  699.                long *nlines)
  700. #else
  701. long nodes_make(nodes,nnodes,ssecs,nssecs,segs,nsegs,verts,nverts,lines,nlines)
  702. DOOM_NODE **nodes;
  703. long *nnodes;
  704. DOOM_SSECTOR **ssecs;
  705. long *nssecs;
  706. DOOM_SEGS **segs;
  707. long *nsegs;
  708. DOOM_VERT **verts;
  709. long *nverts;
  710. DOOM_LINE **lines;
  711. long *nlines;
  712. #endif
  713. {
  714.   NODE_TREE *nodetree;                /* BSP node tree */
  715.   register int i;
  716.  
  717.   ninfo.nsverts = -1;
  718.   for (i = 0; i < *nlines; i++) {        /* find maximum used vertex */
  719.     if (ninfo.nsverts < (*lines)[i].fndx) ninfo.nsverts = (*lines)[i].fndx;
  720.     if (ninfo.nsverts < (*lines)[i].tndx) ninfo.nsverts = (*lines)[i].tndx;
  721.   }
  722.   ninfo.nsverts++;
  723.   ninfo.sverts = blockmem(DOOM_VERT,2*ninfo.nsverts);/* assume no more than  */
  724.   for (i = 0; i < ninfo.nsverts; i++)        /* nsverts new verts created */
  725.     ninfo.sverts[i] = (*verts)[i];
  726.   ninfo.nsegs = nodes_segs_init(*lines,*nlines);/* initialize SEGS list */
  727.   nodetree = tree_branch(nodetree);        /* node tree root */
  728.   nodetree->nsegs = ninfo.nsegs;
  729.   nodetree->segs = ninfo.sinfo;
  730.   nodes_segs_bounds(nodetree);
  731.   printf("%d sides ==>  ",ninfo.nsegs);
  732.   ninfo.nnodes = nodes_partition_node(nodetree)/2;/* BSP it */
  733.   ninfo.nodes = blockmem(DOOM_NODE,ninfo.nnodes);
  734.   ninfo.nssecs = ninfo.nnodes+1;        /* always 1 more SSECTOR */
  735.   ninfo.ssecs = blockmem(DOOM_SSECTOR,ninfo.nssecs);
  736.   ninfo.segs = blockmem(DOOM_SEGS,ninfo.nsegs);
  737.   ninfo.nsegs = ninfo.nssecs = ninfo.nnodes = 0;
  738.   (void)nodes_place_node(ninfo.nodes,&ninfo.nnodes,&ninfo.nssecs,nodetree);
  739.   if (nodes != NULL)  *nodes = ninfo.nodes;
  740.   if (nnodes != NULL) *nnodes = ninfo.nnodes;
  741.   if (ssecs != NULL)  *ssecs = ninfo.ssecs;
  742.   if (nssecs != NULL) *nssecs = ninfo.nssecs;
  743.   if (segs != NULL)   *segs = ninfo.segs;
  744.   if (nsegs != NULL)  *nsegs = ninfo.nsegs;
  745.   if (verts != NULL)  *verts = ninfo.sverts;
  746.   if (nverts != NULL) *nverts = ninfo.nsverts;
  747.   blockfree(nodetree);                /* done with the node tree */
  748.   return *nnodes;                /* return number of nodes */
  749. }
  750.